#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "array.h"

static inline int
smt_element_cmp(smt_element *a, smt_element *b) {
	if(a->key_len == 0 && b->key_len == 0) return 0;
	
	if(a->key_len == 0) return -1;
	if(b->key_len == 0) return 1;
	
	if(a->key_len > b->key_len){
		if(strncmp(a->key, b->key, b->key_len) >= 0) return 1;
		return -1;
	}else if(a->key_len < b->key_len){
		if(strncmp(a->key, b->key, a->key_len) <= 0) return -1;
		return 1;
	}else{
		return strncmp(a->key, b->key, a->key_len);
	}
	return 0;	
}

RB_GENERATE_STATIC(_smt_tree, _smt_element, link, smt_element_cmp);

int smt_array_new(smt_array** a)
{
	smt_array* t = (smt_array*)malloc(sizeof(smt_array));	
	t->elements = NULL;
	t->length = 0;
	t->free_num = 0;
	RB_INIT(&(t->tree));	
	*a = t;
	return 0;
}

static int smt_array_resize(smt_array* a)
{
	int new_size = 0;
	if(a->length <= 0)
	{
		new_size = 16;
	}else if(a->length <1024*1024){
		new_size = a->length * 2;
	}else{
		new_size = a->length + 1024*1024;
	}
	
	smt_element* e = (smt_element*)malloc(sizeof(smt_element)*new_size);
	if(a->length > 0)
	{
		int i;
		memcpy(e, a->elements,  sizeof(smt_element)*a->length);
		//rebuild rbtree
		for(i=0;i<a->length; i++)
		{
			RB_REMOVE(_smt_tree, &(a->tree), a->elements + i);
		}
		for(i=0;i<a->length; i++)
		{
			RB_INSERT(_smt_tree, &(a->tree), e + i);
		}
	}
	a->elements = e;
	a->free_num = new_size - a->length;
	return 0;
}
int smt_array_set(smt_array* a, const char* key, int key_len, void* data)
{
	if(a->free_num == 0) smt_array_resize(a);
	
	if(key_len == 0) //append
	{
		a->elements[a->length].data = data;
		a->elements[a->length].key_len = 0;
		a->length++;
		a->free_num--;
	}else{
		smt_element  k;
		k.key = key;
		k.key_len = key_len;
		smt_element* e = RB_FIND(_smt_tree, &(a->tree), &k);
		
		if(e){
			RB_REMOVE(_smt_tree, &(a->tree), e);
			free(e->key);
			e->key = strndup(key, key_len);
			e->key_len = key_len;
			e->data = data;
			RB_INSERT(_smt_tree, &(a->tree), e);
		}else{
			a->elements[a->length].data = data;
			a->elements[a->length].key = strndup(key,key_len);
			a->elements[a->length].key_len = key_len;
			RB_INSERT(_smt_tree, &(a->tree), &(a->elements[a->length]));
			a->length++;
			a->free_num--;
		}
	}
	return 0;
}

void* smt_array_index_get(smt_array* a, int index)
{
	if(index < a->length ) return a->elements[index].data;
	return NULL;
}
void* smt_array_assoc_get(smt_array* a, const char* key, int key_len)
{
	
	smt_element  k;
	k.key = key;
	k.key_len = key_len;
	smt_element* e = RB_FIND(_smt_tree, &(a->tree), &k);
	if(e)return e->data;
	return NULL;
}
int smt_array_destory(smt_array* a)
{
	return 0;
}
/*
int main()
{
	int i;
	int data[1000];
	smt_array* a;
	char tmp[16];
	smt_array_new(&a);
	for(i=0; i<1000; i++)
	{
		data[i] = i;
		sprintf(tmp, "%d", i);
		smt_array_set(a, tmp, 0, data + i);	
		int* d = smt_array_index_get(a, i);
		if(d){
			printf("%d\n", *d);
		}
	}
	return 0;
}
*/
